﻿#pragma once

#include <cstdlib>
#include <iostream>
#include <cassert>
using namespace std;

namespace Tree
{
	//template<class K , class V>
	template<class K>
	struct Node
	{
		Node(K val)
			:_val(val)
			, _bf(0)
			,_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
		{}

		~Node()
		{

		}

		int _Height(Node<K>* root)
		{
			if (root == nullptr)
				return 0;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);

			return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
		}

		void _InOrder(Node<K>* _root)
		{
			if (_root == nullptr)
			{
				return;
			}

			_InOrder(_root->_left);
			cout << _root->_val << endl;
			_InOrder(_root->_right);
		}

		bool _IsBalanceTree(Node<K>* root)
		{
			// 空树也是AVL树 
			if (nullptr == root)
				return true;
			// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 
			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);
			int diff = rightHeight - leftHeight;


			// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 
			// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树 
			if (abs(diff) >= 2)
			{
				cout << root->_val << "⾼度差异常" << endl;
				return false;
			}
			if (root->_bf != diff)
			{
				cout << root->_val << "平衡因⼦异常" << endl;
				return false;
			}
			// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树 
			return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
		}

		K _val = K();
		int _bf = 0;
		Node<K>* _left = nullptr;
		Node<K>* _right = nullptr;
		Node<K>* _parent = nullptr;
	};

	//template<class K , class V>
	template<class K>
	class AVLTree
	{
	public:
		AVLTree() = default;

		~AVLTree()
		{}

		void inorder()
		{
			_root->_InOrder(_root);
		}

		//// 左单旋
		//void RotateL(Node<K>* parent)
		//{
		//	Node<K>* SubR = parent->_right;
		//	Node<K>* SubRL = SubR->_left;

		//	parent->_right = SubRL;

		//	if (SubRL)
		//		SubRL->_parent = parent;

		//	Node<K>* pParent = parent->_parent;

		//	SubR->_right = parent;
		//	parent->_parent = SubR;
		//	
		//	if (parent == _root)
		//	{
		//		SubR->_parent = nullptr;
		//		_root = SubR;
		//	}
		//	else
		//	{
		//		if (pParent->_left == parent)
		//		{
		//			pParent->_left = SubR;
		//			SubR->_parent = pParent;
		//		}
		//		else if (pParent->_right == parent)
		//		{
		//			pParent->_right = SubR;
		//			SubR->_parent = pParent;
		//		}
		//		else
		//		{
		//			assert(false);
		//		}
		//	}
		//	SubR->_bf = 0;
		//	parent->_bf = 0;
		//}

		//// 右单旋
		//void  RotateR(Node<K>* parent)
		//{
		//	Node<K>* SubL = parent->_left;
		//	Node<K>* SubLR = SubL->_right;

		//	

		//	parent->_left = SubLR;

		//	if (SubLR)
		//		SubLR->_parent = parent;

		//	Node<K>* pParent = parent->_parent;

		//	SubL->_right = parent;
		//	parent->_parent = SubL;

		//	if (parent == _root)
		//	{
		//		SubL->_parent == nullptr;
		//		_root = SubL;
		//	}
		//	else
		//	{
		//		if (pParent->_left == parent)
		//		{
		//			pParent->_left = SubL;
		//		}
		//		else if(pParent->_right == parent)
		//		{
		//			pParent->_right = SubL;
		//		}
		//		else
		//		{
		//			assert(false);
		//		}
		//		SubL->_parent = pParent;
		//	}
		//	SubL->_bf = 0;
		//	parent->_bf = 0;
		//}

		void RotateL(Node<K>* parent)
		{
			Node<K>* subR = parent->_right;
			Node<K>* subRL = subR->_left;
			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

			Node<K>* parentParent = parent->_parent;
			subR->_left = parent;
			parent->_parent = subR;
			if (parentParent == nullptr)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (parent == parentParent->_left)
				{
					parentParent->_left = subR;
				}
				else
				{
					parentParent->_right = subR;
				}
				subR->_parent = parentParent;
			}

			parent->_bf = subR->_bf = 0;
		}

		void RotateR(Node<K>* parent)
		{
			Node<K>* subL = parent->_left;
			Node<K>* subLR = subL->_right;

			parent->_left = subLR;
			if (subLR)
				subLR->_parent = parent;

			Node<K>* pParent = parent->_parent;

			subL->_right = parent;
			parent->_parent = subL;

			if (parent == _root)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (pParent->_left == parent)
				{
					pParent->_left = subL;
				}
				else
				{
					pParent->_right = subL;
				}

				subL->_parent = pParent;
			}

			subL->_bf = 0;
			parent->_bf = 0;
		}


		// 左右双旋
		// 先左旋后右旋
		void RotateLR(Node<K>* parent)
		{
			Node<K>* SubL = parent->_left;
			Node<K>* SubLR = SubL->_right;

			int bf = SubLR->_bf;

			RotateL(parent->_left);
			RotateR(parent);

			if (bf == 0)
			{
				parent->_bf = 0;
				SubL->_bf = 0;
				SubLR->_bf = 0;
			}
			else if (bf == 1)
			{
				parent->_bf = 0;
				SubL->_bf = -1;
				SubLR->_bf = 0;
			}
			else if (bf == -1)
			{
				parent->_bf = 1;
				SubL->_bf = 0;
				SubLR->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}
		// 右左双旋
		void RotateRL(Node<K>* parent)
		{
			Node<K>* SubR = parent->_right;
			Node<K>* SubRL = SubR->_left;

			int bf = SubRL->_bf;

			RotateR(parent->_right);
			RotateL(parent);

			if (bf == 0)
			{
				parent->_bf = 0;
				SubR->_bf = 0;
				SubRL->_bf = 0;
			}
			else if (bf == 1)
			{
				parent->_bf = -1;
				SubR->_bf = 0;
				SubRL->_bf = 0;
			}
			else if (bf == -1)
			{
				parent->_bf = 0;
				SubR->_bf = 1;
				SubRL->_bf = 0;
			}
		}

		int _Height()
		{
			return _root->_Height(_root);
		}

		bool _IsBalanceTree()
		{
			return _root->_IsBalanceTree(_root);
		}


		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node<K>(key);
			}

			Node<K>* cur = _root;
			Node<K>* parent = nullptr;

			while (cur)
			{
				if (key > cur->_val)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_val)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node<K> (key);

			if (key > parent->_val)
				parent->_right = cur;
			else //if (key < parent->_val)
				parent->_left = cur;
			/*else
				assert(false);*/

			cur->_parent = parent;

			while (parent)
			{
				if (parent->_left == cur)
					parent->_bf--;
				else if (parent->_right == cur)
					parent->_bf++;
				else
					assert(false);

				if (parent->_bf == 0)
				{
					break;
				}
				else if (parent->_bf == 1 || parent->_bf == -1)
				{
					cur = parent;
					parent = parent->_parent;
				}
				else if (parent->_bf == 2 || parent->_bf == -2)
				{
					// 右边高了，向左旋
					if (parent->_bf == 2 && cur->_bf == 1)
					{
						RotateL(parent);
					}
					// 左边高了，向右旋
					else if(parent->_bf == -2 && cur->_bf == -1)
					{
						RotateR(parent);
					}
					else if (parent->_bf == 2 && cur->_bf == -1)
					{
						RotateRL(parent);
					}
					else if(parent->_bf == -2 && cur->_bf == 1)
					{
						RotateLR(parent);
					}
					else
					{
						assert(false);
					}
					break;
				}
				else
				{
					assert(false);
				}
			}

			return true;
		}

	private:
		Node<K>* _root = nullptr;
	};



	void test()
	{
		AVLTree<int> t;
		srand(time(NULL));
		int n = 100000;
		clock_t start = clock();

		while (n--)
		{
			int i = rand() + n;
			t.Insert(i);
		}

		clock_t end = clock();
		cout << end - start << endl;
		cout << "Height:" << t._Height() << endl;
		cout << "是否是二叉树：" << t._IsBalanceTree() << endl;
	}
}